class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        // write code here
        vector<int> maxx;
        int n = a.size();
        for(int i = 0;i < n;i++)
        {
            if(maxx.empty())
            {
                maxx.push_back(a[i]);
            }
            else
            {
                if(maxx.back() < a[i])
                {
                    maxx.push_back(a[i]);
                }
                else
                {
                    int l = 0,r = maxx.size() - 1;
                    while(l < r)
                    {
                        int mid = (l + r) >> 1;
                        if(maxx[mid] >= a[i])
                        {
                            r = mid;
                        }
                        else
                        {
                            l = mid + 1;
                        }
                    }
                    maxx[l] = a[i];
                }
            }
        }
        return maxx.size();
    }
};